P2178 [NOI2015] 品酒大会

字符串的贡献在第一个位置,为了与 endpos\text{endpos} 对应上考虑将串翻转。

两杯酒 p,qp,q 的最大相似度就是 lcp(p,q)\text{lcp}(p,q) ,即后缀自动机 parent\text{parent} 树上 lastp,lastqlast_p,last_q 两个节点的 lca\text{lca}

大的相似度会对较小的相似度产生影响,可以看作在后缀树上从深度大的节点考虑。

阅读全文 »

P4248 [AHOI2013]差异

1i<jnlen(Ti)+len(Tj)2×lcp(Ti,Tj)\sum_{1\leqslant i <j\leqslant n}\text{len}(T_i)+\text{len}(T_j)-2\times\text{lcp}(T_i,T_j)

(1i<jnlen(Ti)+len(Tj))21i<jnlcp(Ti,Tj)\left(\sum_{1\leqslant i <j\leqslant n}\text{len}(T_i)+\text{len}(T_j)\right)-2\sum_{1\leqslant i <j\leqslant n}\text{lcp}(T_i,T_j)

阅读全文 »

hdu6715 算术

i=1nj=1mμ(lcm(i,j))=d=1min(n,m)i=1nj=1m[gcd(i,j)=d]μ(ijd)=d=1min(n,m)i=1ndj=1md[gcd(i,j)=1]μ(ijd)=d=1min(n,m)t=1min(nd,md)μ(t)i=1ndtj=1mdtμ(ijdt2)=T=1min(n,m)dTμ(d)i=1nTj=1mTμ(dTij)=T=1min(n,m)i=1nTj=1mTμ(Tij)=T=1min(n,m)μ(T)i=1nTj=1mT[gcd(i,T)=1][gcd(j,T)=1][gcd(i,j)=1]μ(i)μ(j)=T=1min(n,m)μ(T)d=1min(nT,mT)μ(d)[gcd(d,T)=1]i=1nTdj=1mTd[gcd(i,T)=1][gcd(i,d)=1]μ(i)μ(d)[gcd(j,T)=1][gcd(j,d)=1]μ(j)μ(d)=T=1min(n,m)d=1min(nT,mT)μ(Td)μ2(d)i=1nTdj=1mTd[gcd(i,dT)=1]μ(i)[gcd(j,dT)=1]μ(j)=T=1min(n,m)μ(T)dTμ2(d)i=1nTj=1mT[gcd(i,T)=1]μ(i)[gcd(j,T)=1]μ(j)=T=1min(n,m)μ(T)(dTμ2(d))(i=1nT[gcd(i,T)=1]μ(i))(j=1mT[gcd(j,T)=1]μ(j))=T=1min(n,m)μ(T)(dTμ2(d))(i=1nTμ(iT))(j=1mTμ(jT))\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m \mu(\text{lcm}(i,j)) \\

阅读全文 »

P6825 「EZEC-4」求和

i=1nj=1ngcd(i,j)i+j\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)^{i+j}

d=1ni=1nj=1n[gcd(i,j)=d]di+j\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)=d]d^{i+j}

阅读全文 »

CF547C Mike and Foam

cic_iii 毫升泡沫的酒在架子上的瓶数,A=maxi=1naiA=\max_{i=1}^n a_i

为了方便将二元组视为有序,答案除以 22 即可。

i=1Aj=1Acicj[gcd(i,j)=1]\sum_{i=1}^A \sum_{j=1}^A c_i c_j [\gcd(i,j)=1]

阅读全文 »

CF439E Devu and Birthday Celebration

i1=1ni2=1n...if=1n[ai=n][gcdai=1]\sum_{i_1=1}^n\sum_{i_2=1}^n...\sum_{i_f=1}^n [\sum{a_i}=n][\gcd{a_i}=1]

i1=1ni2=1n...if=1n[ai=n]dgcdaiμ(d)\sum_{i_1=1}^n\sum_{i_2=1}^n...\sum_{i_f=1}^n [\sum{a_i}=n]\sum_{d|\gcd{a_i}} \mu(d)

阅读全文 »